|
== Motivation == The task of linear system solution is a classical task of linear algebra. There are a variety of known methods for linear system solution. The choice of the method depends essentially on the set of numbers used. More precise it depends on the algebraic structure of the variables and coefficients. The solution of system in fields and bodies, for example, in rational or real numbers is the most studied. These algebraic structures allow the everywhere defined operation of division. It is convenient to develop the simple and powerful methods. Precise and approximate methods are distinguished. The most popular is Gauss method consisting in consequent elimination of variables and obtaining the triangular form of the matrix. Ring algebraic structures such as integer numbers require special methods, as the division is not the everywhere-defined operation in a ring. There is known the universal method using unimodular transformations of matrix to obtain Smith normal form. Result matrix has diagonal form and allow the simple representation of solutions. Unfortunately this method is exponential. Up to present time were suggested a few more complex but polynomial methods. The development of such areas of computer science as Petri net theory, logic programming, artificial intellect require to solve integer systems over the set of nonnegative integer numbers. Nonnegative integer numbers form algebraic structure of monoid. In monoid even the operation of subtraction is not everywhere defined. All the known methods of integer system solution in nonnegative integer numbers are exponential. Therefore, the task of the effective methods development for linear system solution, especially in nonnegative numbers, is enough significant. Decomposition into clans〔(Zaitsev D.A. ) (Solving Linear Systems via Composition of their Clans, Intelligent Information Management, 2009, 1, 73-80. )〕 allows an essential acceleration of computations. In the case the exponential complexity of the source method of system solution the acceleration is exponential too. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Matrix decomposition into clans」の詳細全文を読む スポンサード リンク
|